/**
 * file :	dlist.h
 * author :	bushaofeng
 * created :	2013-04-20 11:26
 * func :       双向链表，分已用表和未用表
 */

#ifndef	__DLIST_H_
#define	__DLIST_H_

#include <stdio.h>
#include <assert.h>

#define DLIST_DEF_SIZE  10240

template<typename T>
class DList{
    private:
        typedef struct _item_t{
            T                   item;
            struct _item_t*     prev;
            struct _item_t*     next;
        }_item_t;
    public:
        DList(size_t size=DLIST_DEF_SIZE){
            assert(init(size));
        }
        ~DList(){
            delete[] m_list;
        }

        bool init(size_t size=DLIST_DEF_SIZE){
            m_list = new _item_t[size];
            if(m_list==NULL){
                return false;
            }

            m_size = size;
            m_unused_len = m_size;
            m_inused_len = 0;

            m_unused_head.next = m_list;
            m_list[0].prev = &m_unused_head;
            for(size_t i=0; i<m_size-1; i++){
                m_list[i].next = m_list + i+1;
                m_list[i+1].prev = m_list + i;
            }
            m_list[m_size-1].next = NULL;
            m_inused_head.next = NULL;
            return true;
        }

        T* insert(T t){
            _item_t* pt = getUnused();
            if(pt==NULL){
                return NULL;
            }

            addInused(pt);
            pt->item = t;
            return &pt->item;
        }
        
        bool remove(T* pt){
            _item_t* t = (_item_t*)pt;
            delInused(t);
            addUnused(t);
            return true;
        }

        size_t getUnusedLen(){return m_unused_len;}
        size_t getInusedLen(){return m_inused_len;}

        /**
         * 遍历
         */
        inline T* begin(){
            return (T*)m_inused_head.next;
        }
        inline T* next(T* t){
            if(t == NULL) return NULL;
            return (T*)((_item_t*)t)->next;
        }
        inline T* end(){
            return NULL;
        }
        inline bool haveNext(T* t){
            return next(t)==end();
        }

        /**
         * 测试使用
         */
        size_t getUnusedTestLen(){
            _item_t*    p = m_unused_head.next;
            size_t      len = 0;
            while(p){
                len++;
                p = p->next;
            }
            return len;
        }
        size_t getInusedTestLen(){
            _item_t*    p = m_inused_head.next;
            size_t      len = 0;
            while(p){
                len++;
                printf("%d ", p->item);
                p = p->next;
            }
            printf("\n");
            return len;
        }

    private:
        /**
         * delete one item from unused list.
         */
        _item_t* getUnused(){
            if(m_inused_len==m_size){
                return NULL;
            }
            _item_t* item = m_unused_head.next;
            m_unused_head.next = item->next;
            if(item->next){
                item->next->prev = &m_unused_head;
            }
            m_unused_len--;
            return item;
        }
        /**
         * insert one item into inused list.
         */
        _item_t* addInused(_item_t* t){
            if(m_inused_head.next){
                m_inused_head.next->prev = t;
            }
            t->next = m_inused_head.next;
            t->prev = &m_inused_head;
            m_inused_head.next = t;
            m_inused_len++;
            return t;
        }

        _item_t* delInused(_item_t* t){
            if(t->next){
                t->next->prev = t->prev;
            }
            t->prev->next = t->next;
            m_inused_len--;
            return t;
        }

        _item_t* addUnused(_item_t* t){
            if(m_unused_head.next){
                m_unused_head.next->prev = t;
            }
            t->next = m_unused_head.next;
            t->prev = &m_unused_head;
            m_unused_head.next = t;
            m_unused_len++;
            return t;
        }
        
    private:
        _item_t*        m_list;
        _item_t         m_inused_head;
        _item_t         m_unused_head;
        size_t          m_size;
        size_t          m_inused_len;
        size_t          m_unused_len;
};

#endif
